{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 15.1 Rod cutting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.1-1\n",
    "\n",
    "> Show that equation (15.4) follows from equation (15.3) and the initial condition $T(0) = 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For $n=0$, $T(0) = 2^0 = 1$.\n",
    "\n",
    "Suppose $T(i) = 2^i$ for $i$ in $[0, n - 1]$, then\n",
    "$$\n",
    "T(n) = 1 + \\sum_{j=0}^{n-1} T(j) = 1 + 1 + 2 + 2^2 + \\cdots + 2^{n-1} = 2^n - 1 + 1 = 2^n\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.1-2\n",
    "\n",
    "> Show, by means of a counterexample, that the following \"greedy\" strategy does not always determine an optimal way to cut rods. Define the density of a rod of length $i$ to be $p_i/i$, that is, its value per inch. The greedy strategy for a rod of length $n$ cuts off a first piece of length $i$, where $1 \\le i \\le n$, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length $n - i$ ."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $p_1  = 1, p_2 = 8, p_3 = 14, p_4 = 0$, the densities $p_1 / 1 = 1, p_2 / 4 = 2, p_3 / 3 = 4 \\frac{2}{3}$, for $n=4$, the greedy result is $3$ and $1$, the total value if $15$, and the dynamic programming solution is $2$ and $2$, which is $16$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.1-3\n",
    "\n",
    "> Consider a modification of the rod-cutting problem in which, in addition to a price $p_i$ for each rod, each cut incurs a fixed cost of $c$. The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamic-programming algorithm to solve this modified problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$r_n = \\max(\\max_{1 \\le i \\le {n - 1}} (p_i + r_{n-i}) - c, p_n)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cut_rod(p, n, c):\n",
    "    r = [0 for _ in xrange(n + 1)]\n",
    "    for j in range(1, n + 1):\n",
    "        r[j] = p[j]\n",
    "        for i in range(1, j):\n",
    "            r[j] = max(r[j], p[i] + r[j - i] - c)\n",
    "    return r[n]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.1-4\n",
    "\n",
    "> Modify MEMOIZED-CUT-ROD to return not only the value but the actual solution, too."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cut_rod_sub(p, n, r, s):\n",
    "    if r[n] >= 0:\n",
    "        return r[n]\n",
    "    r[n] = 0\n",
    "    for i in range(1, n + 1):\n",
    "        ret = p[i] + cut_rod_sub(p, n - i, r, s)\n",
    "        if r[n] < ret:\n",
    "            r[n] = ret\n",
    "            s[n] = i\n",
    "    return r[n]\n",
    "\n",
    "\n",
    "def cut_rod(p, n):\n",
    "    r = [-1 for _ in xrange(n + 1)]\n",
    "    s = [i for i in xrange(n + 1)]\n",
    "    cut_rod_sub(p, n, r, s)\n",
    "    r = r[n]\n",
    "    subs = []\n",
    "    while n > 0:\n",
    "        subs.append(s[n])\n",
    "        n -= s[n]\n",
    "    return r, subs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.1-5\n",
    "\n",
    "> The Fibonacci numbers are defined by recurrence (3.22). Give an $O(n)$-time dynamic-programming algorithm to compute the nth Fibonacci number. Draw the subproblem graph. How many vertices and edges are in the graph?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    a, b = 0, 1\n",
    "    for i in range(1, n):\n",
    "        c = a + b\n",
    "        a, b = b, c\n",
    "    return c"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
